package com.njupt.LinkTable;

/**
 * 206.反转链表
 */
public class ReverseList {


    //头插法实现单链表逆置
    public ListNode reverseList(ListNode head) {
        ListNode HEAD = new ListNode(-1);
        ListNode p = head;
        while(p != null){
            ListNode node = new ListNode(p.val);
            node.next = HEAD.next;
            HEAD.next = node;
            p = p.next;
        }
        return HEAD.next;
    }

    //迭代法，原地逆置
    public ListNode reverseList1(ListNode head) {
        ListNode pre = null;
        ListNode p = head;
        ListNode rear = null;
        while(p != null){
            rear = p.next;
            p.next = pre;
            pre = p;
            p = rear;
        }
        return pre;
    }

    public ListNode reverseList2(ListNode head) {
        return reverseCur(null,head);
    }

    public ListNode reverseCur(ListNode pre,ListNode p){
        if(p==null){
            return pre;
        }

        ListNode rear = p.next;
        p.next = pre;
        return reverseCur(p,rear);

    }




    public  void printList(ListNode head){
        ListNode p = head;
        while(p != null){
            System.out.print(p.val + " ");
            p = p.next;
        }
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);

        head.next = node1; node1.next = node2;node2.next = node3;

        ReverseList test = new ReverseList();
        ListNode head1 = test.reverseList2(head);
        test.printList(head1);
    }
}